package cn.edu.zzuli.sort;

import java.util.Arrays;

public class InsertSort {

    public static void main(String[] args) {

        int[] arr = {101, 34, 119, 1};

        //插入排序
        for (int i = 1; i < arr.length ; i++) {
            //插入的值
            int insertVal = arr[i];
            //插入的坐标
            int insertIndex = i - 1;

            //找到要插入的位置, 因为要插入一个值，所以整体都要后移
            while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
                //整体后移，不用担心 arr[insertIndex + 1]也就是 arr[i] 这个值，这个值已经被我们备份到 insertVal了
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }

            //只要运行到这里，说明我们的数组中已经找到了要插入的位置了
            if (insertIndex+1 != i) {
                arr[insertIndex + 1] = insertVal;
            }
            System.out.println("第"+ i + "轮插入排序后~: " + Arrays.toString(arr));
        }

    }

}
